package linear_list.leetcode.medium;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author bruin_du
 * @description 展平多级双向链表
 * @date 2022/8/11 0:33
 **/
public class OfferII028_Flatten {
    static class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;
    };

    public Node flatten(Node head) {
        if (head == null) return head;
        //方法一：递归
        recursion(head);

        //方法二：迭代
        iterate(head);
        return head;
    }

    private Node recursion(Node node) {
        if (node == null || (node.child == null && node.next == null)) return node;
        Node next = node.next;
        //child结点不为空,递归child结点
        if (node.child != null) {
            //返回的是末尾结点
            Node ret = recursion(node.child);
            node.next = node.child;
            node.child.prev = node;
            //如果末尾结点不为空,才需要拼接
            if (ret != null) ret.next = next;
            //如果下一个当前层的下一个结点为空,遍历child结点,否则拼接
            if (next != null) next.prev = ret;
            else next = ret;
            node.child = null;
        }
        //否则遍历下一个结点,并返回末尾结点
        return recursion(next);
    }

    private void iterate(Node head) {
        Deque<Node> stack = new ArrayDeque<>();
        Node cur = head;
        while (cur.next != null || cur.child != null || !stack.isEmpty()) {
            if (cur.child != null) {
                if (cur.next != null) stack.push(cur.next);
                //连接child结点
                cur.next = cur.child;
                cur.child.prev = cur;
                cur.child = null;
            } else if (cur.next == null) {
                //连接末尾结点
                Node node = stack.pop();
                cur.next = node;
                node.prev = cur;
            }
            //前面有child和末尾结点都连接过了,直接往后遍历即可
            cur = cur.next;
        }
    }
}
